home *** CD-ROM | disk | FTP | other *** search
/ Personal Computer World 2008 February / PCWFEB08.iso / Software / Freeware / Miro 1.0 / Miro_Installer.exe / xulrunner / python / BitTorrent / bitfield.py < prev    next >
Encoding:
Python Source  |  2007-11-12  |  3.6 KB  |  155 lines
  1. # Written by Bram Cohen, Uoti Urpala, and John Hoffman
  2. # see LICENSE.txt for license information
  3.  
  4. try:
  5.     True
  6. except:
  7.     True = 1
  8.     False = 0
  9.     bool = lambda x: not not x
  10.  
  11. try:
  12.     sum([1])
  13.     negsum = lambda a: len(a)-sum(a)
  14. except:
  15.     negsum = lambda a: reduce(lambda x,y: x+(not y), a, 0)
  16.     
  17. def _int_to_booleans(x):
  18.     r = []
  19.     for i in range(8):
  20.         r.append(bool(x & 0x80))
  21.         x <<= 1
  22.     return tuple(r)
  23.  
  24. lookup_table = [_int_to_booleans(i) for i in range(256)]
  25.  
  26. reverse_lookup_table = {}
  27. for i in xrange(256):
  28.     reverse_lookup_table[lookup_table[i]] = chr(i)
  29.  
  30.  
  31. class Bitfield:
  32.     def __init__(self, length, bitstring = None):
  33.         self.length = length
  34.         if bitstring is not None:
  35.             extra = len(bitstring) * 8 - length
  36.             if extra < 0 or extra >= 8:
  37.                 raise ValueError
  38.             t = lookup_table
  39.             r = []
  40.             for c in bitstring:
  41.                 r.extend(t[ord(c)])
  42.             if extra > 0:
  43.                 if r[-extra:] != [0] * extra:
  44.                     raise ValueError
  45.                 del r[-extra:]
  46.             self.array = r
  47.             self.numfalse = negsum(r)
  48.         else:
  49.             self.array = [False] * length
  50.             self.numfalse = length
  51.  
  52.     def __setitem__(self, index, val):
  53.         val = bool(val)
  54.         self.numfalse += self.array[index]-val
  55.         self.array[index] = val
  56.  
  57.     def __getitem__(self, index):
  58.         return self.array[index]
  59.  
  60.     def __len__(self):
  61.         return self.length
  62.  
  63.     def tostring(self):
  64.         booleans = self.array
  65.         t = reverse_lookup_table
  66.         s = len(booleans) % 8
  67.         r = [ t[tuple(booleans[x:x+8])] for x in xrange(0, len(booleans)-s, 8) ]
  68.         if s:
  69.             r += t[tuple(booleans[-s:] + ([0] * (8-s)))]
  70.         return ''.join(r)
  71.  
  72.     def complete(self):
  73.         return not self.numfalse
  74.  
  75.  
  76. def test_bitfield():
  77.     try:
  78.         x = Bitfield(7, 'ab')
  79.         assert False
  80.     except ValueError:
  81.         pass
  82.     try:
  83.         x = Bitfield(7, 'ab')
  84.         assert False
  85.     except ValueError:
  86.         pass
  87.     try:
  88.         x = Bitfield(9, 'abc')
  89.         assert False
  90.     except ValueError:
  91.         pass
  92.     try:
  93.         x = Bitfield(0, 'a')
  94.         assert False
  95.     except ValueError:
  96.         pass
  97.     try:
  98.         x = Bitfield(1, '')
  99.         assert False
  100.     except ValueError:
  101.         pass
  102.     try:
  103.         x = Bitfield(7, '')
  104.         assert False
  105.     except ValueError:
  106.         pass
  107.     try:
  108.         x = Bitfield(8, '')
  109.         assert False
  110.     except ValueError:
  111.         pass
  112.     try:
  113.         x = Bitfield(9, 'a')
  114.         assert False
  115.     except ValueError:
  116.         pass
  117.     try:
  118.         x = Bitfield(7, chr(1))
  119.         assert False
  120.     except ValueError:
  121.         pass
  122.     try:
  123.         x = Bitfield(9, chr(0) + chr(0x40))
  124.         assert False
  125.     except ValueError:
  126.         pass
  127.     assert Bitfield(0, '').tostring() == ''
  128.     assert Bitfield(1, chr(0x80)).tostring() == chr(0x80)
  129.     assert Bitfield(7, chr(0x02)).tostring() == chr(0x02)
  130.     assert Bitfield(8, chr(0xFF)).tostring() == chr(0xFF)
  131.     assert Bitfield(9, chr(0) + chr(0x80)).tostring() == chr(0) + chr(0x80)
  132.     x = Bitfield(1)
  133.     assert x.numfalse == 1
  134.     x[0] = 1
  135.     assert x.numfalse == 0
  136.     x[0] = 1
  137.     assert x.numfalse == 0
  138.     assert x.tostring() == chr(0x80)
  139.     x = Bitfield(7)
  140.     assert len(x) == 7
  141.     x[6] = 1
  142.     assert x.numfalse == 6
  143.     assert x.tostring() == chr(0x02)
  144.     x = Bitfield(8)
  145.     x[7] = 1
  146.     assert x.tostring() == chr(1)
  147.     x = Bitfield(9)
  148.     x[8] = 1
  149.     assert x.numfalse == 8
  150.     assert x.tostring() == chr(0) + chr(0x80)
  151.     x = Bitfield(8, chr(0xC4))
  152.     assert len(x) == 8
  153.     assert x.numfalse == 5
  154.     assert x.tostring() == chr(0xC4)
  155.